#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
//windows will stack overflow. Linux OK
long long f[10000000];
long long  pell(int n)
{
	if(1 == n || 2 == n) return n;
	if(f[n]) return f[n];
	f[n] = (2*pell(n - 1) + pell(n - 2)) % 32767;
	return f[n];
}
void work1()
{
	int n, x;
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf("%d", &x);
		printf("%d\n", pell(x));
	}
}

int main()
{
   work1();
   return 0;
}

